ACdream 1114 Number theory （莫比乌斯反演）

Posted on | In , ,

给你一个序列 a，求出这个序列中互质数的有多少对。
其中所有的整数的都小于等于 222222 。

题解

  • 设$f(d)$为$\gcd$恰好为$d$的对数
  • 设$F(d)$为$\gcd$为$d$的倍数的对数
  • 所以$F(d)=\sum _{d|n}f(n)$
  • 莫比乌斯反演可得，$f(d)=\sum_{d|n} \mu(\frac{n}{a})·F(n)$
  • 问题求的为$f(1)$，即$\sum \mu(n)·F(n)$
  • $F(n)$ 可以用 $cnt[i]$: 这个序列中 $i$ 的个数，$num[i]$: 表示这个序列中为 $i$ 的倍数的数字的个数，$O(nlogn)$ 既可以处理出所有的 $F(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 没测过不一定对
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn = 1e5+7;

const int N = 222222+10;
int isprime[N],mu[N],prime[N], tot; //isprime[i]:i是否为素数。mu[]:莫比乌斯函数。tot素数个数

int n, a[maxn], num[N], cnt[N];
ll ans=0;


void Mobius(int n)
{
    int i,j;
    tot=0;mu[1]=1;
    for(i=2;i<=n;i++){
        if(!isprime[i]){
            prime[tot++]=i;
            mu[i]=-1;
        }
        for(j=0; j<tot && i*prime[j]<=n;j++){
            isprime[i*prime[j]]=1;
            if(i%prime[j])  mu[i*prime[j]]=-mu[i];
            else    {mu[i*prime[j]]=0;break;}
        }
    }
}

int main()
{
    Mobius(N-5);
    scanf("%d", &n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
    }
    for(int i=1;i<N;i++)
    {
        for(int j=i;j<N;j+=i)
         num[i]+=cnt[j];
    }
    for(int i=1;i<N;i++)
        ans+=(mu[i]*1LL*num[i]*(num[i]-1))/2;
    printf("%lld\n", ans);
    return 0;
}